package 回溯;

import java.util.ArrayList;
import java.util.List;

public class q131分割回文串 {
    class Solution {
        List<List<String>> lists = new ArrayList<>();
        List<String> path = new ArrayList<>();

        public List<List<String>> partition(String s) {

            backTracking(s, 0);
            return lists;
        }

        public void backTracking(String s, int startIndex) {

            if (startIndex >= s.length()) {
                lists.add(new ArrayList<>(path));
                return;
            }

            for (int i = startIndex; i < s.length(); i++) {
                if (isPalindrome(s, startIndex, i)) {
                    path.add(s.substring(startIndex, i + 1));
                    //起始位置后移，保证不重复
                    backTracking(s, i + 1);
                    path.remove(path.size() - 1);
                }

            }
        }

        public boolean isPalindrome(String s, int left, int right) {
            while (left < right) {
                if (s.charAt(left) != s.charAt(right)) {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }
    }
}
